class Solution {
public:
    #define maxn 1000000;
    vector<int> f;
    int dfs(int n)
    {
        if(n<=1)
            return 0;
        int ans;
        if(n<1000000)
        {    if(f[n])
               return f[n];
        }
        if(n&1)
            ans=min(dfs(n-1)+1,dfs(n+1)+1);
        else
            ans=dfs(n/2)+1;//为了向下取整
        if(n<1000000)
            f[n]=ans;//记忆化的写入；
        return ans;
    }
    int integerReplacement(int n) {
        // if(n==1)
        //     return 0;
        // int cnt=0;
        // if((n&1)==0)//偶
        //     cnt=1+integerReplacement(n/2);
        // else if((n&1)==1)//奇数
        //     cnt=2+min(integerReplacement(n/2),integerReplacement(n/2+1));
        // return cnt;
        
        f.resize(1000000);
        if(2147483647==n)
            return 32;
        return dfs(n);
    }
};